Согласно преданию, при помощи учителя Пифагор с острова Самос перебрался на Лесбос, где жил у своего родственника Зоила. Там Пифагор познакомился с поэтом и философом Ферекидом Сиросским — другом Фалеса Милетского. У Ферекида Пифагор учился астрологии, предсказанию затмений, тайнам чисел, медицине и другим обязательным для того времени наукам. Прожив на Лесбосе несколько лет, Пифагор отправился в Милет — к знаменитому Фалесу. Пифагор слушал лекции милетского мудреца, которому было далеко за семьдесят, и его более молодого коллегу Анаксимандра. Впрочем, большинство историков сомневается, что Пифагор обучался у Ферекида и Фалеса. Например, Ион, впервые упомянувший Ферекида рядом с Пифагором, еще ничего не говорит об их личных контактах. Но уже в следующем веке историк Андрон из Эфеса, автор книги о семи мудрецах, называет Ферекида учителем Пифагора. Таким образом, ничего определенного об учителях Пифагора сказать нельзя. Несмотря на его несомненную близость к ионийской традиции и знакомство с идеями милетских философов, никто из них, вероятно, не был его прямым наставником.
Все путешествия Пифагора относят ко времени его жизни на Самосе. В поздние времена Пифагору приписывали поездки не только к египтянам, финикийцам или персидским магам, но и к вавилонянам, эфиопам, сирийцам, индийцам, евреям, иберам, фракийцам, арабам и даже галльским жрецам-друидам. По дороге в Египет Пифагор на некоторое время останавливается в Финикии, где, по преданию, учился у знаменитых сидонских жрецов. Пока он жил в Финикии, его друзья добились того, что Поликрат — властитель Самоса, не только простил беглеца, но даже послал ему рекомендательные письма для Амазиса — фараона Египта.
В Египте благодаря покровительству Пифагор познакомился с мемфисскими жрецами. Ему удалось проникнуть в «святая святых» — египетские храмы, куда чужестранцы не допускались. Для этого Пифагор прошел посвящение в сан жреца. Изучив язык и выдержав все искусы на пути к познанию, Пифагор стал равноправным членом касты жрецов. Пребывание в Египте способствовало тому, что он сделался одним из самых образованных людей своего времени.
После смерти фараона Амазиса его преемник отказался выплачивать ежегодную дань Камбизу, персидскому царю, что послужило поводом для войны. Персы не пощадили даже священные храмы. Подверглись гонениям и жрецы их убивали или брали в плен. Так попал в персидский плен и Пифагор. Согласно легендам, в плену в Вавилоне Пифагор встречался с персидскими магами, познакомился с учениями халдейских мудрецов, со знаниями, накопленными восточными народами в течение многих веков астрономией и астрологией, медициной и арифметикой. Эти науки у халдеев в значительной степени опирались на представления о магических и сверхъестественных силах, они придали определенное мистическое звучание философии и математике Пифагора.
Пифагора освободил персидский царь Дарий Гистасп, прослышавший о знаменитом греке.